/**
 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 **回文串** 。
返回 s 所有可能的分割方案。
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]
 */

/**
 * 1. 分割操作 等同于组合问题
 *【终止条件】每个元素都分割完， index>=s.length
 * 2. 判断回文数： 可以用dp处理s[i..j]的是否是回文数
 */
/**
 * 快速判断回文数
const isPal = (s) =>{
  return s===s.split('').reverse().join('')
} 
 */
var partition = function(s) {
  const isPalindrome = computedPalindrome(s);
  const res = [];
  const path = [];
  const backTrack = (index) => {
    if(index>=s.length) {
      res.push(path.slice());
      return;
    }
    for(let i=index; i<s.length; i++) {
      if(isPalindrome[index][i]){
        path.push(s.slice(index, i+1));
        backTrack(i+1);
        path.pop();
      }
    }
  }
  backTrack(0);
  return res;
};
// 外层倒叙（内层正序） 保证 i～j中间已经计算过
function computedPalindrome(s) {
  const m = s.length;
  const dp = Array(m).fill().map(() => Array(m).fill(false));
  // 保证 i～j中间已经计算过
  for(let i = m-1; i>=0;i--) { //倒叙遍历
    for(let j=i; j<m;j++) { // 从当前指针往前遍历
      if(s[i]==s[j] && (j-i<2 || dp[i+1][j-1])){
        dp[i][j] = true;
      }
    }
  }
  return dp
}

const s = "aab";
console.log('分割回文串', partition(s));
